package OJpractice;

import java.util.*;

public class Practice {

    /**
     * 只出现一次的数字
     */

    // 方法1：使用for循环+异或^
    public int singleNumber1(int[] nums) {
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            ret ^= nums[i];
        }
        return ret;
    }

    // 方法2：使用Map（因为要统计词频）：HashMap、TreeMap都ok
    public int singleNumber(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        // 首先遍历一遍记录
        // 再遍历一遍查看value是1的数据
        for (int i = 0; i < nums.length; i++) {
            // 判断之前是否已经出现过
            if(map.get(nums[i]) == null) {
                // 没有出现
                map.put(nums[i],1);
            } else {
                // 出现了就增加value值
                // 注意map.get获取到的是频率value
                int value = map.get(nums[i]);
                map.put(nums[i],value+1);
            }
        }
        // 再进行一次遍历查看value==1的数据key
        for (int i = 0; i < nums.length; i++) {
            if(map.get(nums[i])==1) {
                return nums[i];
            }
        }
        return -1;
    }

    // 方法3：使用Set：遍历看有没有该元素，有就删掉已经放入的数据，没有就进行添加
    // 时间复杂度：O(N*logN)；N遍历、logN查找
    public int singleNumber2(int[] nums) {
        Set<Integer> set = new TreeSet<>();
        // 也可以是HashSet：速度更快 时间复杂度是O(N)
        //Set<Integer> set = new HashSet<>();

        for (int i = 0; i < nums.length; i++) {
            int key = nums[i];
            if(!set.contains(key)) {
                // 还不存在就添加
                set.add(key);
            } else {
                // 已经存在就删除
                set.remove(key);
            }
        }
        // 来到这儿：说明set还剩一个数据
        // 问题：如何找到这个数据：再次遍历数据，看是否包含在set集合中，包含就输出
        for (int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])) {
                return nums[i];
            }
        }
        // 来到这儿说明：没有找到
        return -1;
    }


    /**
     * 复制带随机指针的链表
     */
    /*public Node copyRandomList(Node head) {
        // Map用于存储新老结点
        // 这里不能使用TreeMap，因为TreeMap的key要是可以比较的，而这里的自定义类型Node不需要进行比较，
        // 也没有实现Comparable接口重写compareTo方法
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        // 第一次遍历链表：新建结点+map存储
        while(cur != null) {
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        // 第二次遍历链表：修改对应关系
        cur = head; // cur必须回到head位置！！
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next; // 注意循环变化的条件！！
        }
        // 返回新的头结点
        return map.get(head);
    }*/


    /**
     * 宝石与石头：
     * 找石头中有多少个宝石：宝石放到集合Set中，遍历石头并与宝石进行比较，相同就数量++
     */
    public int numJewelsInStones(String jewels, String stones) {
        // 把宝石放到Set集合中:但是注意是将String拆成char类型的进行零散存储、进行零散比较
        Set<Character> set = new HashSet<>();
        // 注意使用for-each进行遍历：元素类型是插入，但是数组是要（String.toChararray()）进行转换的。
        for (char ch : jewels.toCharArray()) {
            set.add(ch);
        }
        // 遍历石头：与宝石进行比较，相同就数量++
        int count = 0;
        for (char ch : stones.toCharArray()) {
            if(set.contains(ch)) {
                // 包含就++
                count++;
            }
        }
        return count;
    }


    /**
     * 坏键盘打字：
     */
    class Main {
        // 查找坏键盘
        private static void findBad(String str1, String str2) {
            // 集合Set中放入实际输入的
            Set<Character> set = new HashSet<>();
            // 注意：因为最后要求的是大写形式，所以在存入集合前就将其全部变成大写的形式，然后再转为字符数组
            for (char ch : str2.toUpperCase().toCharArray()) {
                set.add(ch);
            }
            // 遍历期望输入的字符串，同样转为大写，和集合中的字符进行比较
            Set<Character> setBad = new HashSet<>();
            for (char ch : str1.toUpperCase().toCharArray()) {
                /*if(!set.contains(ch)) {
                    // 如果不包含在实际输入中说明是坏键，应该打印
                    // 但是要注意会存在一个问题：会出现重复打印
                    // 为了避免坏键重复：再使用一个集合Set存储坏键，每次在实际输入中不包含时就与坏键集合对比，
                    // 坏键集合中也不包含时就存入坏键集合并进行输出
                    if(!setBad.contains(ch)) {
                        setBad.add(ch);
                        System.out.print(ch);
                    }
                }*/

                // 这里可以修改为：
                if(!set.contains(ch) && !setBad.contains(ch)) {
                    System.out.print(ch);
                    setBad.add(ch);
                }
            }
        }

        public static void main(String[] args) {
            // 要进行两行字符串的输入
            Scanner scanner = new Scanner(System.in);
            while(scanner.hasNextLine()) {
                String str1 = scanner.nextLine(); // 期望输入
                String str2 = scanner.nextLine(); // 实际输入
                // 进行查找坏键盘:注意实际使用的地方是在循环中！！
                findBad(str1,str2);
            }
        }
    }




    /**
     * 前k个高频单词：
     * 返回前k个出现次数最多的单词
     * 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
     * （词频）：Map
     *
     * 之前学过topK问题：使用大小根堆 、 优先队列 （前k大：大根堆  升序：大根堆）
     */
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>(); // 存储单词以及出现次数
        // 进行数组遍历：如果出现过就value+1，没有出现过put
        for (String key : words) {
            if(map.get(key) == null) {
                map.put(key,1);
            } else {
                int val = map.get(key);
                map.put(key,val+1);
            }
        }
        // 数据放到优先级队列中（前k大：小根堆！！）
        // 小根堆的原因：小的在堆顶，而比较就与堆顶比较，换掉堆顶后再向下进行小堆排序，小的再换到堆顶，依次进行

        // 其实也就是建立一个大小为k的小根堆:注意小根堆中的数据类型
        // 优先级队列默认是小根堆
        PriorityQueue<Map.Entry<String,Integer>> minQue =
                new PriorityQueue<>(k,new Comparator<Map.Entry<String, Integer>>() {
                    @Override
                    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                        //return o1.getValue()-o2.getValue(); // 比较词频
                        // 但是注意引用类型比较大小compareTo！！
                        /*return o1.getValue().compareTo(o2.getValue());
                         */

                        // 进行改写：
                        // 同频就比较key的字母顺序
                        if(o1.getValue().compareTo(o2.getValue()) == 0) {
                            // 词频一样，把字母顺序大的方在堆顶（因为最后要倒转)
                            return (o2.getKey().compareTo(o1.getKey()));
                            // 注意是o2-o1：因为是小根堆排序方式<0就小根堆（小于的在堆顶）
                        }
                        // 如果不相等 就进行频率比较返回
                        return o1.getValue().compareTo(o2.getValue());
                    }
                });

        // 遍历map集合，先给小根堆放满k个，然后从第（k+1）个开始和堆顶元素比较
        // 注意map的遍历方式
        for (Map.Entry<String,Integer> entry : map.entrySet()) {
            if(minQue.size() < k) {
                // 还没有放满,则继续放入
                minQue.offer(entry);
            } else {
                // 已经放满：当前元素就与堆顶元素比较
                Map.Entry<String,Integer> top = minQue.peek();
                // 换入大的把小的弹出，自动向下排序

                // 意思也就是说（小根堆的堆顶是最小的数据，把大于的换进去，最小的元素弹出来，剩下的就是较大的）
                if(entry.getValue().compareTo(top.getValue()) > 0) {
                    // 大于就进行替换（弹出堆顶元素，放入新的元素）
                    minQue.poll();
                    minQue.offer(entry);
                } else {
                    // == or <
                    // < 不放入   == 要考虑情况:按照字典顺序排序
                    // 引用类型：compareTo
                    // 相同词频时，弹出字母大的，放入小的
                    if(top.getValue().compareTo(entry.getValue())==0) {
                        // 引用类型：compareTo
                        if(top.getKey().compareTo(entry.getKey())>0) {
                            // 字典顺序小的放入,大的弹出
                            minQue.poll();
                            minQue.offer(entry);
                        }
                    }
                }
            }
        }
        // 遍历比较完成，小根堆ok
        // 但是要输出频率最高->最低，输出的只是单词String,存入链表后进行反转
        List<String> ret = new LinkedList<>(); // 最后只输出单词，并不输出词频
        for (int i = 0; i < k; i++) {
            ret.add(minQue.poll().getKey());
        }
        // 小根堆：从小到大排序，但是实际要求是从大到小，需要进行反转：
        Collections.reverse(ret); // 反转链表，大的在前
        return ret;
    }

    public static void main(String[] args) {
        String[] words = {"hello","top","nice","top","hi","top","nice","hello"};
        Practice practice = new Practice();
        List<String> ret = practice.topKFrequent(words,3);
        System.out.println(ret);
        // 注意：当存在两个相同频率的单词时，在弹出堆顶元素后会存在一个问题，频率一样的两个单词谁去堆顶呢？
        // 注意查看poll方法的源码：注意到在向下调整过程中经历重写的compareTo方法时比较的只是频率val值
        // 此时因为两个单词的词频一样就会直接返回，没有进行过新的排序，所以可能就会存在输出顺序不对的问题
        // 所以：要重新调整冲那个鞋的compareTo方法
    }



    /**
     * 字符串中只出现一次的第一个字符：
     * 返回的是该字符在字符串中的下标！
     * 不用HashMap，而是使用一个数组进行存储字符数量
     */
    public int firstUniqChar(String str) {
        // 遍历字符串（转数组）进行数量统计
        int[] count = new int[26];
        // ‘a':97
        for (char ch : str.toCharArray()) {
            count[ch-97]++;
        }

        /*// 遍历字符串获取字符也可以改为：
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            count[ch-97]++;
        }*/

        // 再次遍历字符串 找数组中首次==1的并返回
        /*for (char ch : str.toCharArray()) {
            if(count[ch-97] == 1) {
                return ch;
            }
        }*/

        // 遍历字符串获取字符也可以改为：
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if(count[ch-97]==1) {
                return i; // 返回下标
            }
        }
        return -1;
    }
}
